'''
Company: TWL
Author: xue jian
Email: xuejian@kanzhun.com
Date: 2020-11-10 08:37:12
'''
#
# @lc app=leetcode.cn id=31 lang=python3
#
# [31] 下一个排列
#

# @lc code=start
from typing import List
# 从根本上说，这个题就是寻找最少位数的最右侧的连续数组，这个数组可以变换出更大的值，然后求可以变换的
# 所有值中最小的一个。
# 这样题解就合理了，首先从右向左做遍历，寻找第一个nums[i]<nums[i+1]的位置，这个
# 时候nums[i:]是一个存在更高排列方式的数组。然后按规则找他的最小最高即可。
class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        if len(nums)<=1:
            return
        i, j = len(nums)-2, len(nums)-1
        while i>=0:
            if nums[i]<nums[i+1]:
                break
            i-=1
        if i<0:
            start, end = 0, len(nums)-1
            while start<end:
                nums[start], nums[end] = nums[end], nums[start]
                start+=1
                end-=1
            return
        while j>i:
            if nums[i]<nums[j]:
                break
            j-=1
        nums[i], nums[j] = nums[j], nums[i]
        start, end = i+1, len(nums)-1
        while start<end:
            nums[start], nums[end] = nums[end], nums[start]
            start+=1
            end-=1
        return


# @lc code=end

